Théorème de Knaster-Tarski

Le théorème de Knaster-Tarski est un théorème de point fixe pour une application croissante d'un treillis complet dans lui-même. Il est nommé d'après Bronislaw Knaster et Alfred Tarski.

Histoire

Bronisław Knaster (1893-1980).

Alfred Tarski (1901-1983).

Knaster et Tarski, deux mathématiciens amis en Pologne, ont proposé la première version du théorème en 1928. Le théorème de Knaster-Tarski est aussi appelé simplement théorème de point fixe de Tarski, le théorème ayant été publié par Tarski dans sa forme générale en 1955. En 1955, Anne C. Davis montre une sorte de réciproque.

En fait, Moschovakis, dans son livre de théorie des ensembles cité dans la bibliographie, fait remonter ce type de théorème de point fixe à la démonstration par Zermelo de son théorème éponyme, et ne nomme à ce sujet aucun autre mathématicien, sans doute pour éviter la loi de Stigler.

Énoncé

L'énoncé de Knaster-Tarski n'est pas le plus puissant du genre^{[C'est-à-dire ?]} mais il est relativement simple :

Si $T$ est un treillis complet et $f:T\to T$ une application croissante, alors le sous-ensemble ordonné des points fixes de $f$ est un treillis complet (donc non vide).

En particulier, $f$ a un plus petit et un plus grand point fixe.

Démonstrations

La démonstration usuelle^{[réf. nécessaire]} est non constructive^{[réf. nécessaire]}:

Soit $F$ l'ensemble des points fixes de $f$. Montrons que dans $F$, toute partie $G$ possède une borne supérieure. Pour cela, notons $m$ la borne inférieure de l'ensemble $S:=\{x\in T\mid x\geq G\quad {\text{et}}\quad f(x)\leq x\}$. Alors :

• $m\geq G$ (car $S\geq G$) ;
• $f(m)\leq m$. En effet, $f(m)\leq S$ car pour tout $x\in S$, d'une part $f(m)\leq f(x)$ (car $m\leq x$) et d'autre part $f(x)\leq x$ ;
• $f(m)\geq m$. En effet, $f(m)\in S$ car (d'après les deux points précédents) $f(m)\geq f(G)=G$ et $f(f(m))\leq f(m)$ ;
• tout point fixe de $f$ qui majore $G$ appartient à $S$ donc est minoré par $m$.

Par conséquent, $m$ est la borne supérieure de $G$ dans $F$.

Une seconde démonstration, d'un théorème plus faible, est la suivante : on démontre par récurrence transfinie que $f$ a un point fixe.

On pose $x_{0}=$ le plus petit élément de $T$, puis on construit une « fonction » $x$ par récursion transfinie comme suit : si $\alpha$ est un ordinal quelconque, $x_{\alpha +1}:=f(x_{\alpha })$, et si $\alpha$ est un ordinal limite, $x_{\alpha }$ est la borne supérieure de $\{x_{\beta }\mid \beta <\alpha \}$. D'après le choix de $x_{0}$ et la croissance de $f$, $\alpha \mapsto x_{\alpha }$ est croissante. En choisissant un ordinal qui ne s'injecte pas dans $T$ (par exemple son ordinal de Hartogs), on voit que $\alpha \mapsto x_{\alpha }$ ne peut pas être injective et donc il existe $\gamma <\beta$ tels que $x_{\gamma }=x_{\beta }$. Par croissance de $\alpha \mapsto x_{\alpha }$, $x_{\gamma }\leq x_{\gamma +1}\leq x_{\beta }=x_{\gamma }$ donc $x_{\gamma }=x_{\gamma +1}=f(x_{\gamma })$ : on a trouvé un point fixe.

Applications

En mathématiques

On peut démontrer le théorème de Cantor-Bernstein en appliquant celui de Knaster-Tarski : voir le § « Deuxième démonstration » de l'article sur ce théorème.

En informatique

Les principaux domaines d'applications sont la sémantique des langages de programmation et l'analyse de programme (en) par interprétation abstraite ou model checking, domaines qui se recouvrent fortement.

Bibliographie

• (en) Charalambos D. Aliprantis et Kim C. Border, Infinite Dimensional Analysis : A Hitchhiker's Guide, Springer, 2007, 3^e éd. (lire en ligne), p. 17-18
• (en) Alfred Tarski, « A lattice-theoretical fixpoint theorem and its applications », Pacific J. Math., vol. 5, n^o 2,‎ 1955, p. 285-309 (lire en ligne)
• (en) Yiannis N. Moschovakis, Notes on Set Theory, Springer, 1994 (lire en ligne)
• B. Knaster, « Un théorème sur les fonctions d'ensembles », Ann. Soc. Polon. Math., vol. 6,‎ 1928, p. 133-134 (lire en ligne) — Knaster expose des résultats obtenus avec Tarski.